<!DOCTYPE html>
<html lang="en-US">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width,initial-scale=1">
    <title>108. 将有序数组转换为二叉搜索树 | 悄悄的卷，然后卷死所有人</title>
    <meta name="description" content="这是一个奇怪的地方">
    <link rel="stylesheet" href="/blobview/assets/style.019f39fc.css">
    <link rel="modulepreload" href="/blobview/assets/Home.d05cdc04.js">
    <link rel="modulepreload" href="/blobview/assets/app.a4363fd4.js">
    <link rel="modulepreload" href="/blobview/assets/fe_suanfa_将有序数组转换为二叉搜索树.md.6a79c21d.lean.js">
    <link rel="modulepreload" href="/blobview/assets/app.a4363fd4.js">
    <meta name="twitter:title" content="108. 将有序数组转换为二叉搜索树 | 悄悄的卷，然后卷死所有人">
    <meta property="og:title" content="108. 将有序数组转换为二叉搜索树 | 悄悄的卷，然后卷死所有人">
  </head>
  <body>
    <div id="app"><!--[--><div class="theme"><header class="nav-bar" data-v-675d8756><div class="sidebar-button" data-v-675d8756><svg class="icon" xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z" class></path></svg></div><a class="nav-bar-title" href="/blobview/" aria-label="悄悄的卷，然后卷死所有人, back to home" data-v-675d8756 data-v-4a583abe><!----> 悄悄的卷，然后卷死所有人</a><div class="flex-grow" data-v-675d8756></div><div class="nav" data-v-675d8756><nav class="nav-links" data-v-675d8756 data-v-eab3edfe><!--[--><div class="item" data-v-eab3edfe><div class="nav-link" data-v-eab3edfe data-v-b8818f8c><a class="item" href="/blobview/" data-v-b8818f8c>Home <!----></a></div></div><div class="item" data-v-eab3edfe><div class="nav-dropdown-link" data-v-eab3edfe data-v-56bf3a3f><button class="button" data-v-56bf3a3f><span class="button-text" data-v-56bf3a3f>前端君</span><span class="right button-arrow" data-v-56bf3a3f></span></button><ul class="dialog" data-v-56bf3a3f><!--[--><li class="dialog-item" data-v-56bf3a3f><div class="nav-dropdown-link-item" data-v-56bf3a3f data-v-bbc27490><a class="item" href="/blobview/fe/secondary/interviews/network" data-v-bbc27490><span class="arrow" data-v-bbc27490></span><span class="text" data-v-bbc27490>面试八股文</span><span class="icon" data-v-bbc27490><!----></span></a></div></li><li class="dialog-item" data-v-56bf3a3f><div class="nav-dropdown-link-item" data-v-56bf3a3f data-v-bbc27490><a class="item" href="/blobview/fe/algorithm" data-v-bbc27490><span class="arrow" data-v-bbc27490></span><span class="text" data-v-bbc27490>算法大卷</span><span class="icon" data-v-bbc27490><!----></span></a></div></li><li class="dialog-item" data-v-56bf3a3f><div class="nav-dropdown-link-item" data-v-56bf3a3f data-v-bbc27490><a class="item" href="/blobview/fe/errormd/chrome插件开发指南" data-v-bbc27490><span class="arrow" data-v-bbc27490></span><span class="text" data-v-bbc27490>坑你太美</span><span class="icon" data-v-bbc27490><!----></span></a></div></li><!--]--></ul></div></div><div class="item" data-v-eab3edfe><div class="nav-dropdown-link" data-v-eab3edfe data-v-56bf3a3f><button class="button" data-v-56bf3a3f><span class="button-text" data-v-56bf3a3f>稀奇君</span><span class="right button-arrow" data-v-56bf3a3f></span></button><ul class="dialog" data-v-56bf3a3f><!--[--><li class="dialog-item" data-v-56bf3a3f><div class="nav-dropdown-link-item" data-v-56bf3a3f data-v-bbc27490><a class="item" href="/blobview/fe/secondary/interviews/network" data-v-bbc27490><span class="arrow" data-v-bbc27490></span><span class="text" data-v-bbc27490>web3</span><span class="icon" data-v-bbc27490><!----></span></a></div></li><!--]--></ul></div></div><div class="item" data-v-eab3edfe><div class="nav-link" data-v-eab3edfe data-v-b8818f8c><a class="item" href="/blobview/b" data-v-b8818f8c>杂谈君 <!----></a></div></div><!--]--><!----><!----></nav></div><!--[--><!--]--></header><aside class="sidebar" data-v-83e92a68><nav class="nav-links nav" data-v-83e92a68 data-v-eab3edfe><!--[--><div class="item" data-v-eab3edfe><div class="nav-link" data-v-eab3edfe data-v-b8818f8c><a class="item" href="/blobview/" data-v-b8818f8c>Home <!----></a></div></div><div class="item" data-v-eab3edfe><div class="nav-dropdown-link" data-v-eab3edfe data-v-56bf3a3f><button class="button" data-v-56bf3a3f><span class="button-text" data-v-56bf3a3f>前端君</span><span class="right button-arrow" data-v-56bf3a3f></span></button><ul class="dialog" data-v-56bf3a3f><!--[--><li class="dialog-item" data-v-56bf3a3f><div class="nav-dropdown-link-item" data-v-56bf3a3f data-v-bbc27490><a class="item" href="/blobview/fe/secondary/interviews/network" data-v-bbc27490><span class="arrow" data-v-bbc27490></span><span class="text" data-v-bbc27490>面试八股文</span><span class="icon" data-v-bbc27490><!----></span></a></div></li><li class="dialog-item" data-v-56bf3a3f><div class="nav-dropdown-link-item" data-v-56bf3a3f data-v-bbc27490><a class="item" href="/blobview/fe/algorithm" data-v-bbc27490><span class="arrow" data-v-bbc27490></span><span class="text" data-v-bbc27490>算法大卷</span><span class="icon" data-v-bbc27490><!----></span></a></div></li><li class="dialog-item" data-v-56bf3a3f><div class="nav-dropdown-link-item" data-v-56bf3a3f data-v-bbc27490><a class="item" href="/blobview/fe/errormd/chrome插件开发指南" data-v-bbc27490><span class="arrow" data-v-bbc27490></span><span class="text" data-v-bbc27490>坑你太美</span><span class="icon" data-v-bbc27490><!----></span></a></div></li><!--]--></ul></div></div><div class="item" data-v-eab3edfe><div class="nav-dropdown-link" data-v-eab3edfe data-v-56bf3a3f><button class="button" data-v-56bf3a3f><span class="button-text" data-v-56bf3a3f>稀奇君</span><span class="right button-arrow" data-v-56bf3a3f></span></button><ul class="dialog" data-v-56bf3a3f><!--[--><li class="dialog-item" data-v-56bf3a3f><div class="nav-dropdown-link-item" data-v-56bf3a3f data-v-bbc27490><a class="item" href="/blobview/fe/secondary/interviews/network" data-v-bbc27490><span class="arrow" data-v-bbc27490></span><span class="text" data-v-bbc27490>web3</span><span class="icon" data-v-bbc27490><!----></span></a></div></li><!--]--></ul></div></div><div class="item" data-v-eab3edfe><div class="nav-link" data-v-eab3edfe data-v-b8818f8c><a class="item" href="/blobview/b" data-v-b8818f8c>杂谈君 <!----></a></div></div><!--]--><!----><!----></nav><!--[--><!--]--><ul class="sidebar-links" data-v-83e92a68><!--[--><li class="sidebar-link"><a class="sidebar-link-item" href="#核心思想">核心思想</a><!----></li><li class="sidebar-link"><a class="sidebar-link-item" href="#为什么要选择有序数组中间的值？">为什么要选择有序数组中间的值？</a><!----></li><li class="sidebar-link"><a class="sidebar-link-item" href="#代码例子">代码例子</a><!----></li><!--]--></ul><!--[--><!--]--></aside><div class="sidebar-mask"></div><main class="page" data-v-7eddb2c4><div class="container" data-v-7eddb2c4><!--[--><!--]--><div style="position:relative;" class="content" data-v-7eddb2c4><div><h1 id="_108-将有序数组转换为二叉搜索树" tabindex="-1">108. 将有序数组转换为二叉搜索树 <a class="header-anchor" href="#_108-将有序数组转换为二叉搜索树" aria-hidden="true">#</a></h1><h2 id="核心思想" tabindex="-1">核心思想 <a class="header-anchor" href="#核心思想" aria-hidden="true">#</a></h2><p>当我们在处理一道类似于排序数组的问题时，我们可以考虑使用二分查找的思路。在这道题目中，我们可以使用二分查找的思路构建一棵平衡的二叉搜索树。</p><p>具体地，我们可以选择有序数组的中间元素作为二叉搜索树的根节点，并且将数组分为左右两部分。然后，中间元素左侧的所有元素构成二叉搜索树的左子树，中间元素右侧的所有元素构成二叉搜索树的右子树。接着，我们可以递归地构建左子树和右子树，直到没有子树为止。最后我们得到的二叉搜索树就是一棵平衡的树。</p><p>这是因为，当我们选中数组的中间元素作为根节点时，左右两侧的元素个数应该是相同的(中间元素既是左子树的最右端节点，也是右子树的最左端节点)，因此生成的树是平衡的。</p><p>二叉搜索树的特点是：左子树的所有节点的值均小于根节点的值，右子树的所有节点的值均大于根节点的值。因此，我们可以使用二叉搜索树的性质，使查找某个元素的时间复杂度降到最低。</p><p>以上就是这道题目的大致思路。</p><h2 id="为什么要选择有序数组中间的值？" tabindex="-1">为什么要选择有序数组中间的值？ <a class="header-anchor" href="#为什么要选择有序数组中间的值？" aria-hidden="true">#</a></h2><p>选择有序数组的中间元素作为二叉搜索树的根节点是一种常见的处理方式，它的本质思想是基于二分查找。同时也要满足二叉搜索树的基本性质，即根节点的左子树值都小于根节点的值，右子树值都大于根节点的值。</p><p>在有序数组中，如果我们选取最小的元素作为根节点，则所有节点都会在右子树上；如果选取最大的元素作为根节点，则所有节点都会在左子树上。这两种情况都违背了满足二叉搜索树的基本性质。</p><p>对于选择中间元素作为根节点，因为有序数组中的元素是按升序排列的，所以中间元素左边的所有元素都比它小，中间元素右边的所有元素都比它大。这样就保证了根节点的左右子树都包含相当数量的元素，并且二叉搜索树的深度最小，保证了平衡性。</p><h2 id="代码例子" tabindex="-1">代码例子 <a class="header-anchor" href="#代码例子" aria-hidden="true">#</a></h2><div class="language-js"><pre><code><span class="token comment">// 定义 sortedArrayToBST 函数</span>
<span class="token keyword">function</span> <span class="token function">sortedArrayToBST</span><span class="token punctuation">(</span><span class="token parameter">nums</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token comment">// 调用 dfs 函数，并将返回结果作为函数的返回值</span>
  <span class="token keyword">return</span> <span class="token function">dfs</span><span class="token punctuation">(</span>nums<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> nums<span class="token punctuation">.</span>length <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token comment">// 定义 dfs 函数，传入参数为 nums 数组、最小下标 lo 和最大下标 hi</span>
<span class="token keyword">function</span> <span class="token function">dfs</span><span class="token punctuation">(</span><span class="token parameter">nums<span class="token punctuation">,</span> lo<span class="token punctuation">,</span> hi</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token comment">// 如果 lo 大于 hi，返回 null</span>
  <span class="token keyword">if</span> <span class="token punctuation">(</span>lo <span class="token operator">&gt;</span> hi<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">return</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
  <span class="token punctuation">}</span>
  <span class="token comment">// 以升序数组的中间元素作为根节点 root</span>
  <span class="token keyword">let</span> mid <span class="token operator">=</span> Math<span class="token punctuation">.</span><span class="token function">floor</span><span class="token punctuation">(</span><span class="token punctuation">(</span>lo <span class="token operator">+</span> hi<span class="token punctuation">)</span> <span class="token operator">/</span> <span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token keyword">let</span> root <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">TreeNode</span><span class="token punctuation">(</span>nums<span class="token punctuation">[</span>mid<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token comment">// 递归的构建 root 的左子树与右子树</span>
  root<span class="token punctuation">.</span>left <span class="token operator">=</span> <span class="token function">dfs</span><span class="token punctuation">(</span>nums<span class="token punctuation">,</span> lo<span class="token punctuation">,</span> mid <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
  root<span class="token punctuation">.</span>right <span class="token operator">=</span> <span class="token function">dfs</span><span class="token punctuation">(</span>nums<span class="token punctuation">,</span> mid <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> hi<span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token comment">// 返回构建好的树</span>
  <span class="token keyword">return</span> root<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre></div><p>来看一看具体的执行步骤以及输出。</p><ol><li><p>首先，我们调用 sortedArrayToBST(nums) 函数，并将输入数组 nums = [-10,-3,0,5,9] 传入。这里 nums 数组中的元素已经是按照升序排列的。下面是每个步骤的执行情况：</p></li><li><p>调用 dfs(nums, 0, 4) 函数，得到最小下标 lo=0，最大下标 hi=4。</p></li><li><p>计算中间元素的下标：mid = Math.floor((0 + 4) / 2) = 2。此时，nums[2] = 0，将其作为根节点。这里使用了 Math.floor() 函数向下取整，以确保 mid 是整数。</p></li><li><p>递归地构建 left 子树。调用 dfs(nums, 0, 1) 函数。得到 lo=0，hi=1。</p></li><li><p>计算中间元素的下标：mid = Math.floor((0 + 1) / 2) = 0。此时，nums[0] = -10，将其作为 left 子树的根节点。</p></li><li><p>递归地构建 left 的 left 子树，调用 dfs(nums, 0, -1) 函数。因为 lo &gt; hi，所以返回 null。</p></li><li><p>递归地构建 left 的 right 子树，调用 dfs(nums, 1, 1) 函数。因为 lo = hi，所以返回 null。</p></li><li><p>left 子树构建完成，将其赋值给根节点的 left 指针。</p></li><li><p>递归地构建 right 子树，调用 dfs(nums, 3, 4) 函数。得到 lo=3，hi=4。</p></li><li><p>计算中间元素的下标：mid = Math.floor((3 + 4) / 2) = 3。此时，nums[3] = 5，将其作为 right 子树的根节点。</p></li><li><p>递归地构建 right 的 left 子树，调用 dfs(nums, 3, 2) 函数。因为 lo &gt; hi，所以返回 null。</p></li><li><p>递归地构建 right 的 right 子树，调用 dfs(nums, 4, 4) 函数。因为 lo = hi，所以返回 null。</p></li><li><p>right 子树构建完成，将其赋值给根节点的 right 指针。</p></li></ol><p>至此，二叉搜索树的构建完成，将其返回作为函数的结果。输出结果为：</p><pre><code>      0
     / \
   -10  5
       / \
      3   9
</code></pre><p>注意到因为有多个根节点，我们选择左侧的元素作为根节点。</p></div></div><footer class="page-footer" data-v-7eddb2c4 data-v-fb8d84c6><div class="edit" data-v-fb8d84c6><div class="edit-link" data-v-fb8d84c6 data-v-1ed99556><!----></div></div><div class="updated" data-v-fb8d84c6><!----></div></footer><!----><!--[--><!--]--></div></main></div><!----><!--]--></div>
    <script>__VP_HASH_MAP__ = JSON.parse("{\"fe_algorithm.md\":\"e1054222\",\"fe_errormd_chrome插件开发指南.md\":\"8310a77a\",\"fe_errormd_mysql密码遗忘.md\":\"37b8860e\",\"fe_secondary_javascript_descriptors.md\":\"cd9a7474\",\"fe_secondary_javascript_javascript.md\":\"42853649\",\"fe_secondary_javascript_jicheng.md\":\"1cd0c4dc\",\"fe_secondary_javascript_jscopy.md\":\"66795111\",\"fe_secondary_javascript_js数据类型.md\":\"c6bc851f\",\"fe_secondary_javascript_let const var 的区别.md\":\"685e3545\",\"fe_secondary_javascript_weakmap.md\":\"2a0ba820\",\"fe_secondary_javascript_作用域.md\":\"220cfcf9\",\"fe_secondary_javascript_变量提升.md\":\"b63f20ee\",\"fe_secondary_javascript_闭包.md\":\"5404cbcf\",\"fe_secondary_python_基础知识.md\":\"ae39dc27\",\"fe_secondary_vite_vite杂烩记录.md\":\"aa7cf9a4\",\"fe_secondary_webpack_loader与plugin的不同.md\":\"e2712a7c\",\"fe_secondary_interviews_jstype.md\":\"b3e700ba\",\"fe_secondary_interviews_mianshi.md\":\"218f21c3\",\"fe_secondary_interviews_modular.md\":\"38434f4f\",\"fe_secondary_interviews_network.md\":\"d5842ea6\",\"fe_suanfa_tree树结构.md\":\"d41c852f\",\"fe_suanfa_二分查找.md\":\"28f745d1\",\"fe_suanfa_二叉树.md\":\"836f7969\",\"fe_suanfa_二叉树后序遍历.md\":\"af43c381\",\"fe_suanfa_二叉树展开链表.md\":\"cc410293\",\"fe_suanfa_二叉树最小深度.md\":\"d272316f\",\"fe_suanfa_二叉树的所有路径.md\":\"70f2feac\",\"fe_suanfa_二叉树的最大深度.md\":\"ab1fe25c\",\"fe_suanfa_冒泡排序.md\":\"b91ecca4\",\"fe_suanfa_前中后序遍历.md\":\"997426ab\",\"fe_suanfa_前缀和.md\":\"6ec90ae8\",\"fe_suanfa_区域和检索数组不可变.md\":\"6e447cdb\",\"fe_suanfa_反转数组.md\":\"c28c7d5f\",\"fe_suanfa_将有序数组转换为二叉搜索树.md\":\"6a79c21d\",\"fe_suanfa_差分.md\":\"101d6b54\",\"fe_suanfa_快速排序.md\":\"575fe1af\",\"fe_suanfa_插入排序.md\":\"078511c5\",\"fe_suanfa_滑动窗口.md\":\"08f684ff\",\"fe_suanfa_翻转二叉树.md\":\"1a866015\",\"fe_suanfa_选择排序.md\":\"a25eac11\",\"fe_suanfa_链表反转.md\":\"a642cc7a\",\"fe_web3_ethers_01-hellovitalik.md\":\"162c31f8\",\"fe_web3_ethers_02-合约交互.md\":\"08f30902\",\"fe_web3_ethers_03-发送eth.md\":\"fbf8825d\",\"index.md\":\"64947f2b\"}")</script>
    <script type="module" async src="/blobview/assets/app.a4363fd4.js"></script>
    
  </body>
</html>